package com.datastructures2.test;

import com.datastructures2.背包队列栈.Queue;

/**
 * 顺序查找（基于无需链表）
 * 未命中和命中都需要N次比较
 * 命中最坏需要N次比较
 *
 * @author MaoLin Wang
 * @date 2020/3/118:01
 */
public class SequentialSearchST<Key, Value> {

    private Node first;
    private int size;


    private class Node {
        private Key key;
        private Value value;
        private Node next;

        public Node(Key key, Value value, Node next) {
            this.key = key;
            this.value = value;
            this.next = next;
        }
    }

    public Value get(Key key) {
        if (key == null) {
            return null;
        }
        for (Node temp = first; temp != null; temp = temp.next) {
            if (temp.key.equals(key)) {
                return temp.value;
            }
        }
        return null;
    }

    public void put(Key key, Value value) {
        if (key == null) {
            return;
        }

        for (Node t = first; t != null; t = t.next) {
            if (t.key.equals(key)) {
                t.value = value;
            }
        }

        Node temp = first;
        first = new Node(key,value,first);
         size++;


    }

    public boolean isEmpty() {
        return size==0;
    }

    private int size() {
        return size;
    }

    public boolean contains(Key key) {
        for (Node temp=first;temp!=null;temp=temp.next){
            if (temp.key.equals(key)){
                return true;
            }
        }
        return false;
    }

    public void delete(Key key) {
        if (key==null)return;
        first=delete(first,key);

    }

    private Node delete(Node first, Key key) {
        if (first==null){
            return null;
        }
        if (first.key.equals(key)){
            first=first.next;
        }
        first.next=delete(first.next,key);
        return first;
    }

    public void print(){
        Node temp=first;
        while (temp!=null){
            System.out.println(temp.key+"->"+temp.value);
            temp=temp.next;
        }
    }

    public static void main(String[] args) {
        SequentialSearchST<String, Integer> searchST = new SequentialSearchST<>();
        searchST.put("a",1);
        searchST.put("f",5);
        searchST.put("c",6);
        searchST.put("d",4);
        searchST.print();
        searchST.delete("c");
        searchST.print();

    }
}
